package algorithm.dynamic_programming;

public class SplitSumClosed {

    public static int ways(int[] arr){
        if(arr == null || arr.length <= 2)
            return 0;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        return process(arr, 0, sum / 2);
    }

    public static int process(int[] arr, int index, int rest){
        if(index == arr.length)
            return 0;
        int process1 = process(arr, index + 1, rest);
        int process2 = 0;
        if (rest - arr[index] >= 0)
            process2 = arr[index] + process(arr, index + 1, rest - arr[index]);
        return Math.max(process1, process2);
    }

    public static int ways2(int[] arr){
        if(arr == null || arr.length <= 2)
            return 0;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        sum = sum / 2;
        int[][] dp = new int[arr.length + 1][sum + 1];
        for (int i = dp.length - 2; i >= 0; i--) {
            for (int j = 0; j < dp[0].length; j++) {
                int a = dp[i + 1][j];
                int b = 0;
                if(j - arr[i] >= 0)
                    b = arr[i] + dp[i + 1][j - arr[i]];
                dp[i][j] = Math.max(a, b);
            }
        }

        return dp[0][sum];
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 5};
        System.out.println(ways(arr));
        System.out.println(ways2(arr));
    }
}
